package org.chnxi.study.leetcode.questions50.ques28;

/**
 * 使用KMP算法进行查找
 *
 * 执行用时：11 ms, 在所有 Java 提交中击败了7.49%的用户
 * 内存消耗：39.8 MB, 在所有 Java 提交中击败了5.43%的用户
 */
public class Simple01 {

    public static void main(String[] args) {
        String sour = "hello";
        String targ = "ll";
        int res = strStr(sour , targ);
        System.out.println("sourceStr="+sour+"; targetStr="+targ+"; idx="+res);

        sour = "aaaaaa";
        targ = "baa";
        res = strStr(sour , targ);
        System.out.println("sourceStr="+sour+"; targetStr="+targ+"; idx="+res);

        sour = "a";
        targ = "";
        res = strStr(sour , targ);
        System.out.println("sourceStr="+sour+"; targetStr="+targ+"; idx="+res);
    }

    public static int strStr(String haystack, String needle) {
        if(haystack == null || needle == null){
            return -1;
        }else if(needle.length() < 1 || haystack.equals(needle)){
            return 0;
        }

        int[] next = kmpNext(needle);

        for (int i = 0, j = 0; i < haystack.length() && j<next.length; i++){

            while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
                j = next[j-1];
            }

            if(haystack.charAt(i) == needle.charAt(j)){
                j++;
            }
            if(j == needle.length()){
                return i - j + 1;
            }
        }

        return -1;
    }

    /**
     * 获取一个字符串（子串）的部分匹配值表
     */
    public static int[] kmpNext(String dest){
        if(dest == null || dest.length() < 1){
            return new int[0];
        }
        //创建一个next数组保存部分匹配值
        int[] next = new int[dest.length()];
        //如果字符串长度为1，部分匹配值就是0
        next[0] = 0;

        for(int i=1 , j=0; i<dest.length(); i++){
            // 需要从next[j-1]获取新的j
            // 直到dest.charAt(i) == dest.charAt(j)后退出
            while(j>0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j-1];
            }
            // 部分匹配值+1
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }

            next[i] = j;
        }
        return next;
    }

}
